НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені  ІГОРЯ СІКОРСЬКОГО”                     ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів”             Тема: «МЕТОДИ ПОШУКУ У МАСИВАХ» Варіант 18              Мета: Отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку. Теоретична частина Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів. Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є: Час, необхідний на впорядкування n-елементного масиву. Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є — це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритмизазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного. Необхідність додаткової пам'яті для сортування. Зазвичай необхідно O(1) пам'яті. Стабільність (англ. Stability) — стабільне сортування не змінює взаємного розташування елементів з однаковими ключами. За час : Сортування вибором — (англ. Selectionsort) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку. Сортування вставкою(включенням) — (англ. Insertionsort) — Визначаємо місце де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди. Сортування обміном (сортування бульбашкою, англ. Bubblesort) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку. Завдання до лабораторної роботи: 1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом. / Блок-схема / / Оцінка складності Назва методу Розмір матриці Час виконання  Бар’єром 10x10 1.7е-04   50x50 4.1е-04   100x100 9,1е-04  Рабіна-Карпа 10x10 2.5е-04   50x50 5.7е-04   100x100 9.3е-04   Результат роботи / / Висновок: Було написано програму, що шукає задане значення в матриці методами бар’єру та Рабіна-Карпа. Обидва алгоритми перевірені на швидкість. Програмний код https://replit.com/join/saemtspjmf-okseniait #include <stdio.h> #include <math.h> #include <time.h> #define BLU "\e[0;34m" #define WHT "\e[0;37m" int main(void) { int L=100; int arr1[L][L]; int arr2[L][L]; int i, j, k, t, n, m, key1; for(i=0; i<L; i++){ for(j=0; j<L; j++){ arr1[i][j]=rand()%50+1; arr2[i][j]=rand()%40+10; } } printf("Завдання 1\n"); clock_t start = clock(), diff; printf("Введіть шуканий елемент: "); scanf("%d", &key1); for(i=0; i<L; i++){ for(j=0; j<L; j++){ if(arr1[i][j]==key1){ printf(BLU"%d \t"WHT, arr1[i][j]); } else{ printf("%d \t", arr1[i][j]); } } printf("\n"); } printf("\n"); for(i=0; i<L; i++){ t=arr1[i][L-1]; arr1[i][L-1]=key1; for(j=0; arr1[i][j]!=key1; j++){ } if(j!=(L-1) || key1 == t){ printf("Елемент %d знайдено у рядку %d, у стовпчику %d\n", key1, i+1, j+1); } arr1[i][L-1]=t; } diff = clock() - start; int msec1 = diff * 1000000 / CLOCKS_PER_SEC; printf("\nЗавдання 2\n"); //clock_t start = clock(), diff; int l; int key2[l]; for(k=0; k<L; k++){ for (i=1; i<L; i++){ t = arr2[k][i]; for (j=i-1; j>=0 && arr2[k][j]>t; j--){ arr2[k][j+1] = arr2[k][j]; } arr2[k][j+1] = t; } } printf("Введіть послідовність: "); l=2; for(i=0; i<l; i++){ scanf("%d", &ke...